Quantum Computing by Clegg Brian;

Author:Clegg, Brian;
Language: eng
Format: epub
Publisher: Icon Books Ltd
Published: 2021-06-15T00:00:00+00:00

The prime un-multiplier

The other well-known algorithm for quantum computers from the early days, predating Grover’s by two years, was Peter Shor’s factorisation algorithm. Like Grover, Shor was working at AT&T’s Bell Labs and in 1994 he showed how a quantum computer would be able to work out which two prime numbers had been multiplied together to produce a particular outcome. As we have seen, this would be a hugely significant outcome if it were practical to achieve with very large numbers, as it is extremely hard to extricate the two primes from the multiplication, a fact relied on by the current encryption used on the internet. The encryption technique typically uses variants of an algorithm called RSA, named after its inventors, Ronald Rivest, Adi Shamir and Leonard Adleman.

The three computer scientists developed RSA at the Massachusetts Institute of Technology (MIT) in 1977, though in fairness it should be mentioned that the mechanism was actually developed three years before this at the UK’s intelligence centre, GCHQ, by Clifford Cocks. Unfortunately for Cocks, the algorithm was considered useful for national security by his superiors, so it was kept secret until the RSA trio had made their approach public, by which time Cocks missed out on any potential patent benefits.

Working through the entire mechanism of RSA is a little fiddly, but at its heart it depends on the person who is going to receive an encrypted message taking two extremely large prime numbers§ and multiplying them together. The resultant huge number is given out freely, along with some other information required to work the algorithm, but only the recipient knows the values of the two primes that were multiplied together. The clever thing about this public/private key approach is that you can give the key to encrypt the information to anyone, but the different key required to decrypt it, is kept secret. The RSA algorithm uses the extremely large multiple to encipher the message in a way that it can only be deciphered if you are aware of the two primes that were multiplied together, which are only known by the recipient of the enciphered message.

Finding the prime factors of a number might not seem too much of a challenge. For example, if the large number were 91, it wouldn’t take too long to work out that the two primes that had been multiplied together were 7 and 13. But with a number that is truly huge, working out the prime factors could take the best computers centuries. At the moment, the most common size for the large number is 2,048 bits of binary – over 600 digits in decimal, though increasingly 4,096-bit public keys are being used and there is no theoretical upper limit. You can always load more bits onto a key, though as the key gets bigger, the time taken to encrypt and decrypt goes up – so there is a balance to be struck.

With Shor’s algorithm, however, the size of keys most typically in use at present can be

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.